<!DOCTYPE html>












  


<html class="theme-next gemini use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222">












<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />






















<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/blog/css/main.css?v=6.3.0" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/blog/images/apple-touch-icon-next.png?v=6.3.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/blog/images/favicon-32x32-next.png?v=6.3.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/blog/images/favicon-16x16-next.png?v=6.3.0">


  <link rel="mask-icon" href="/blog/images/logo.svg?v=6.3.0" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Gemini',
    version: '6.3.0',
    sidebar: {"position":"right","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: 'GBC1F47D02',
      apiKey: '',
      indexName: 'myblog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"请输入关键字","hits_empty":"未找到: ${query}","hits_stats":"${hits} 搜索用时 ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="1python：3.6.2 前言​    排序算法是计算机中最基础的算法，很多高级算法都依赖于此；  排序算法的稳定性 ​    如果待排序的数列中，相同的元素在排序前后相对顺序不变，即为稳定； ​    例如待排序列$[1,2_{a},5,3,2_{b}]$，如果排序之后，$2_{a}$依然在$2_{b}$的前面，就表示稳定；  ​    算法的判断条件很重要，更改了条件，稳定的排序也会变得不稳">
<meta name="keywords" content="sorting">
<meta property="og:type" content="article">
<meta property="og:title" content="内部排序算法">
<meta property="og:url" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/index.html">
<meta property="og:site_name" content="夜行">
<meta property="og:description" content="1python：3.6.2 前言​    排序算法是计算机中最基础的算法，很多高级算法都依赖于此；  排序算法的稳定性 ​    如果待排序的数列中，相同的元素在排序前后相对顺序不变，即为稳定； ​    例如待排序列$[1,2_{a},5,3,2_{b}]$，如果排序之后，$2_{a}$依然在$2_{b}$的前面，就表示稳定；  ​    算法的判断条件很重要，更改了条件，稳定的排序也会变得不稳">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/bubble.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/fast.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/random_quick.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/chose.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/heap.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/insert.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/merge.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/counting.gif">
<meta property="og:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/radix.gif">
<meta property="og:updated_time" content="2018-08-07T14:57:19.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="内部排序算法">
<meta name="twitter:description" content="1python：3.6.2 前言​    排序算法是计算机中最基础的算法，很多高级算法都依赖于此；  排序算法的稳定性 ​    如果待排序的数列中，相同的元素在排序前后相对顺序不变，即为稳定； ​    例如待排序列$[1,2_{a},5,3,2_{b}]$，如果排序之后，$2_{a}$依然在$2_{b}$的前面，就表示稳定；  ​    算法的判断条件很重要，更改了条件，稳定的排序也会变得不稳">
<meta name="twitter:image" content="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/bubble.gif">






  <link rel="canonical" href="https://zhishengqianjun.gitee.io/blog/2018/08/07/algorithm/内部排序算法/"/>



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>内部排序算法 | 夜行</title>
  






  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?03806bd68e029f12f863ba16efac2c2c";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">夜行</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/blog/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">
    <a href="/blog/tags/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />标签</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">
    <a href="/blog/categories/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-th"></i> <br />分类</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/blog/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-about">
    <a href="/blog/about/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-user"></i> <br />关于</a>
  </li>

      
      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />搜索</a>
        </li>
      
    </ul>
  

  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://zhishengqianjun.gitee.io/blog/blog/2018/08/07/algorithm/内部排序算法/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="夜行">
      <meta itemprop="description" content="天行健，君子以自强不息！">
      <meta itemprop="image" content="/blog/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="夜行">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">内部排序算法
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-08-07 21:41:07 / 修改时间：22:57:19" itemprop="dateCreated datePublished" datetime="2018-08-07T21:41:07+08:00">2018-08-07</time>
            

            
              

              
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/blog/categories/sorting/" itemprop="url" rel="index"><span itemprop="name">sorting</span></a></span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/blog/2018/08/07/algorithm/内部排序算法/#comments" itemprop="discussionUrl">
                  <span class="post-meta-item-text">评论数：</span> <span class="post-comments-count valine-comment-count" data-xid="/blog/2018/08/07/algorithm/内部排序算法/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          
            <span class="post-meta-divider">|</span>
            <span class="post-meta-item-icon"
            >
            <i class="fa fa-eye"></i>
             阅读次数： 
            <span class="busuanzi-value" id="busuanzi_value_page_pv" ></span>
            </span>
          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">python：3.6.2</span><br></pre></td></tr></table></figure>
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>​    排序算法是计算机中最基础的算法，很多高级算法都依赖于此；</p>
<blockquote>
<p><strong>排序算法的稳定性</strong></p>
<p>​    如果待排序的数列中，相同的元素在排序前后相对顺序不变，即为稳定；</p>
<p>​    例如待排序列$[1,2_{a},5,3,2_{b}]$，如果排序之后，$2_{a}$依然在$2_{b}$的前面，就表示稳定；</p>
</blockquote>
<p>​    算法的判断条件很重要，更改了条件，稳定的排序也会变得不稳定，如将冒泡的比较变成$\ge$。</p>
<p>​    一图胜千言，在下面搜集了一些简单的示例图，使用gif录屏器制作(算法可视化参见见参考文献)。</p>
<h2 id="1、排序算法的分类"><a href="#1、排序算法的分类" class="headerlink" title="1、排序算法的分类"></a>1、排序算法的分类</h2><p>​    排序算法的理论：</p>
<blockquote>
<ul>
<li><a href="https://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E5%A4%8D%E6%9D%82%E6%80%A7%E7%90%86%E8%AE%BA" target="_blank" rel="noopener">计算复杂性理论</a></li>
<li><a href="https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7" target="_blank" rel="noopener">大O符号</a></li>
<li><a href="https://zh.wikipedia.org/wiki/%E5%85%A8%E5%BA%8F%E5%85%B3%E7%B3%BB" target="_blank" rel="noopener">全序关系</a></li>
<li><a href="https://zh.wikipedia.org/w/index.php?title=%E5%88%97%E8%A1%A8_(%E8%AE%A1%E7%AE%97%E5%99%A8" target="_blank" rel="noopener">列表</a>&amp;action=edit&amp;redlink=1)</li>
<li><a href="https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#.E7.A8.B3.E5.AE.9A.E6.80.A7" target="_blank" rel="noopener">稳定性</a></li>
<li><a href="https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E6%8E%92%E5%BA%8F" target="_blank" rel="noopener">比较排序</a></li>
<li><a href="https://zh.wikipedia.org/w/index.php?title=%E8%87%AA%E9%80%82%E5%BA%94%E6%8E%92%E5%BA%8F&amp;action=edit&amp;redlink=1" target="_blank" rel="noopener">自适应排序</a></li>
<li><a href="https://zh.wikipedia.org/w/index.php?title=%E6%8E%92%E5%BA%8F%E7%BD%91%E7%BB%9C&amp;action=edit&amp;redlink=1" target="_blank" rel="noopener">排序网络</a></li>
<li><a href="https://zh.wikipedia.org/w/index.php?title=%E6%95%B4%E6%95%B0%E6%8E%92%E5%BA%8F&amp;action=edit&amp;redlink=1" target="_blank" rel="noopener">整数排序</a></li>
</ul>
</blockquote>
<p>​    根据排序的方法：插入、交换、选择、合并等, 将排序进行划分：</p>
<table>
<thead>
<tr>
<th>排序方法</th>
<th>排序算法</th>
</tr>
</thead>
<tbody>
<tr>
<td>交换排序</td>
<td>冒泡排序    鸡尾酒排序    奇偶排序    梳排序    侏儒排序    快速排序    臭皮匠排序    Bogo排序</td>
</tr>
<tr>
<td>选择排序</td>
<td>选择排序    堆排序    平滑排序    笛卡尔树排序    锦标赛排序    圈排序</td>
</tr>
<tr>
<td>插入排序</td>
<td>插入排序    希尔排序    伸展排序    二叉查找树排序    图书馆排序    耐心排序</td>
</tr>
<tr>
<td>归并排序</td>
<td>归并排序    梯级归并排序    振荡归并排序    多相归并排序    列表排序</td>
</tr>
<tr>
<td>分布排序</td>
<td>美国旗帜排序    珠排序    桶排序    爆炸排序    计数排序    鸽巢排序    相邻图排序    <br>基数排序    闪电排序    插值排序</td>
</tr>
<tr>
<td>并发排序</td>
<td>双调排序器    Batcher归并网络    两两排序网络</td>
</tr>
<tr>
<td>混合排序</td>
<td>块排序    Tim排序    内省排序    Spread排序    J排序</td>
</tr>
<tr>
<td>其他</td>
<td>拓扑排序    煎饼排序    意粉排序</td>
</tr>
</tbody>
</table>
<p>下面是常用的算法列表：</p>
<blockquote>
<ul>
<li>冒泡排序<ul>
<li>直接冒泡排序</li>
<li>鸡尾酒排序</li>
<li>梳排序</li>
</ul>
</li>
<li>选择排序</li>
<li>插入排序<ul>
<li>直接插入排序</li>
<li>二分插入排序</li>
<li>希尔排序</li>
</ul>
</li>
<li>归并排序</li>
<li>堆排序</li>
<li>快速排序</li>
</ul>
<ul>
<li>计数排序</li>
<li>基数排序</li>
<li>桶排序</li>
</ul>
</blockquote>
<table>
<thead>
<tr>
<th>算法</th>
<th style="text-align:center">最坏时间复杂度</th>
<th style="text-align:center">最佳时间复杂度</th>
<th style="text-align:center">平均时间复杂度</th>
<th style="text-align:center">空间复杂度</th>
<th style="text-align:center">稳定性</th>
</tr>
</thead>
<tbody>
<tr>
<td>冒泡排序</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(n)$</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(1)$</td>
<td style="text-align:center">稳定</td>
</tr>
<tr>
<td>选择排序</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">O(1)</td>
<td style="text-align:center">不稳定</td>
</tr>
<tr>
<td>插入排序</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(n)$</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(1)$</td>
<td style="text-align:center">稳定</td>
</tr>
<tr>
<td>希尔排序</td>
<td style="text-align:center">$O(nlog(n)) \sim O(n^{2})$</td>
<td style="text-align:center">$O(n^{1.5})$</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(1)$</td>
<td style="text-align:center">不稳定</td>
</tr>
<tr>
<td>堆排序</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(1)$</td>
<td style="text-align:center">不稳定</td>
</tr>
<tr>
<td>归并排序</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(n)$</td>
<td style="text-align:center">稳定</td>
</tr>
<tr>
<td>快速排序</td>
<td style="text-align:center">$O(n^{2})$</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(nlog(n))$</td>
<td style="text-align:center">$O(logn)\sim O(n)$</td>
<td style="text-align:center">不稳定</td>
</tr>
<tr>
<td>计数排序</td>
<td style="text-align:center">$O(n+m)$</td>
<td style="text-align:center">$O(n+m)$</td>
<td style="text-align:center">$O(n+m)$</td>
<td style="text-align:center">$O(n + m)$</td>
<td style="text-align:center">稳定</td>
</tr>
<tr>
<td>基数排序</td>
<td style="text-align:center">$O(k*n)$</td>
<td style="text-align:center">$O(k*n)$</td>
<td style="text-align:center">$O(k*n)$</td>
<td style="text-align:center">$O(k*n)$</td>
<td style="text-align:center">稳定</td>
</tr>
<tr>
<td>桶排序</td>
<td style="text-align:center">$O(n)$</td>
<td style="text-align:center">$O(n)$</td>
<td style="text-align:center">$O(n)$</td>
<td style="text-align:center">$O(m)$</td>
<td style="text-align:center">不稳定</td>
</tr>
</tbody>
</table>
<h2 id="2、交换排序"><a href="#2、交换排序" class="headerlink" title="2、交换排序"></a>2、交换排序</h2><h3 id="2-1-冒泡排序"><a href="#2-1-冒泡排序" class="headerlink" title="2.1 冒泡排序"></a>2.1 冒泡排序</h3><p>   <code>Bubble Sort</code></p>
<h4 id="2-1-1-直接冒泡排序"><a href="#2-1-1-直接冒泡排序" class="headerlink" title="2.1.1 直接冒泡排序"></a>2.1.1 直接冒泡排序</h4><p> <img src="/blog/2018/08/07/algorithm/内部排序算法/bubble.gif" alt="bubble"></p>
<p>​    冒泡排序如上图所示，给定一个待排序列，从前往后依次扫描，将最大的元素放到最后面正确的位置，已经放到正确位置的序列在下一次扫描中就不会继续比对。</p>
<blockquote>
<p>待排序列：[4,3,1,2]</p>
<ul>
<li><p>[3,1,2,==4==]</p>
</li>
<li><p>[1,2,==3,4==]</p>
</li>
<li><p>[1,==2,3,4==]</p>
</li>
<li><p>[==1,2,3,4==]</p>
<p>如上面的简单序列所示，黄色的表示已经排好的序列</p>
<p>实际上，我们可以看到，最后一次排序并没有进行元素交换，所以，我们可以设置一个标志位，当本次比对没有进行数据交换的时候，就表明已经有序，跳出程序。</p>
<p>​</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bubble_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    n = len(l_A)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">0</span>,n):</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(<span class="number">0</span>,n-i<span class="number">-1</span>):</span><br><span class="line">            <span class="keyword">if</span> l_A[j] &gt; l_A[j + <span class="number">1</span>]:</span><br><span class="line">                l_A[j + <span class="number">1</span>] , l_A[j] = l_A[j] , l_A[j + <span class="number">1</span>]</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bubble_sort_enhance</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    n = len(l_A)</span><br><span class="line">    swap_flag = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">0</span>,n):</span><br><span class="line">        swap_flag = <span class="number">0</span></span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(<span class="number">0</span>,n-i<span class="number">-1</span>):</span><br><span class="line">            <span class="keyword">if</span> l_A[j] &gt; l_A[j + <span class="number">1</span>]:</span><br><span class="line">                swap_flag = <span class="number">1</span></span><br><span class="line">                l_A[j + <span class="number">1</span>] , l_A[j] = l_A[j] , l_A[j + <span class="number">1</span>]</span><br><span class="line">        <span class="keyword">if</span> swap_flag == <span class="number">0</span>:</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = bubble_sort_enhance(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h4 id="2-1-2-鸡尾酒排序"><a href="#2-1-2-鸡尾酒排序" class="headerlink" title="2.1.2 鸡尾酒排序"></a>2.1.2 鸡尾酒排序</h4><p>​    在调制鸡尾酒的过程中，需要来回摇晃，鸡尾酒算法也叫搅拌排序，涟漪排序</p>
<p>​    鸡尾酒排序是冒泡排序的简单改进，直接冒泡排序是单向的，而鸡尾酒算法则是进行双向排序；</p>
<blockquote>
<p>待排序列：[4,3,2,1]</p>
<ul>
<li><p>[3,2,1,==4==]</p>
</li>
<li><p>[==1==,3,2,==4==]</p>
</li>
<li><p>[==1==,2,==3,4==]</p>
</li>
<li><p>[==1,2,3,4==]</p>
<p>如上图所示，首先进行一次最大数冒泡，将最大数放到最后面，然后进行一次最小数冒泡，将最小数放到左面；</p>
<p>鸡尾酒排序在完全无序的情况下，与直接冒泡排序并无差别，同样的，我们也设置一个交换标志位，在没有交换的情况下，直接跳出。</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">cocktail_sort</span><span class="params">(l_A , n)</span>:</span></span><br><span class="line">    left = <span class="number">0</span></span><br><span class="line">    right = n - <span class="number">1</span></span><br><span class="line">    swap_flag = <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> left &lt; right:</span><br><span class="line">        <span class="keyword">if</span> swap_flag:</span><br><span class="line">            <span class="keyword">for</span> i <span class="keyword">in</span> range(left,right):</span><br><span class="line">                swap_flag = <span class="number">0</span></span><br><span class="line">                <span class="keyword">if</span> l_A[i] &gt; l_A[i + <span class="number">1</span>]:</span><br><span class="line">                    swap_flag = <span class="number">1</span></span><br><span class="line">                    l_A[i] , l_A[i + <span class="number">1</span>]  = l_A[i + <span class="number">1</span>] , l_A[i]</span><br><span class="line">            right = right - <span class="number">1</span></span><br><span class="line"></span><br><span class="line">            <span class="keyword">for</span> i <span class="keyword">in</span> range(right,left,<span class="number">-1</span>):</span><br><span class="line">                <span class="keyword">if</span> l_A[i] &lt; l_A[i - <span class="number">1</span>]:</span><br><span class="line">                    swap_flag = <span class="number">1</span></span><br><span class="line">                    l_A[i] , l_A[i - <span class="number">1</span>]  = l_A[i - <span class="number">1</span>] , l_A[i]</span><br><span class="line">            left = left + <span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = cocktail_sort(A,len(A))</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h4 id="2-1-3-梳排序"><a href="#2-1-3-梳排序" class="headerlink" title="2.1.3 梳排序"></a>2.1.3 梳排序</h4><p>​    <code>Comb Sort</code></p>
<p>​    梳排序也是一种冒泡排序的改进方法，与希尔排序的思想类似，采用不同的增量序列，将待排序列划分成多个子序列，然后将每个子序列使用冒泡排序，最后一次的间隔一定是1，保证最终排序。</p>
<p>​    生成子序列的间隔一般是取待排序列长度递归除以==1.3==得到，例如长度为6的序列，其递减增量序列为：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">6/1.3 = 4.62 =&gt; 4</span><br><span class="line">4/1.3 = 3.07 =&gt; 3</span><br><span class="line">3/1.3 = 2.31 =&gt; 2</span><br><span class="line">2/1.3 = 1.54 =&gt; 1</span><br><span class="line">最终序列为：[4,3,2,1]</span><br></pre></td></tr></table></figure>
<blockquote>
<p>待排序列：[6,5,4,3,2,1]</p>
<ul>
<li><p>[2,1,4,3,6,5]   ==使用间隔4==</p>
</li>
<li><p>[2,1,4,3,6,5]   ==使用间隔3==</p>
</li>
<li><p>[2,1,4,3,6,5]   ==使用间隔2==</p>
</li>
<li><p>[1,2,3,4,5,6]   ==使用间隔1==</p>
<p>如上所示，使用不同的间隔的情况</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">comb_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    gap = int(size/<span class="number">1.3</span>)</span><br><span class="line">    <span class="keyword">while</span> gap &gt;= <span class="number">1</span> :</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">0</span>,size - gap):</span><br><span class="line">            <span class="keyword">if</span> l_A[i] &gt; l_A[i + gap]:</span><br><span class="line">                l_A[i] , l_A[i + gap] = l_A[i + gap] , l_A[i]</span><br><span class="line">        gap = int(gap/<span class="number">1.3</span>)</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = comb_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="2-2-快速排序"><a href="#2-2-快速排序" class="headerlink" title="2.2 快速排序"></a>2.2 快速排序</h3><p>​        <code>Quick Sort</code></p>
<h4 id="2-2-1-快速排序"><a href="#2-2-1-快速排序" class="headerlink" title="2.2.1 快速排序"></a>2.2.1 快速排序</h4><p><img src="/blog/2018/08/07/algorithm/内部排序算法/fast.gif" alt="fast"></p>
<p>​    快速排序算法分治策略(Divide and Conquer)，将一个序列分成两个序列，然后选取基准，使用基准，将小于等于基准的放到左面，大于等于基准的数，放到右面；</p>
<p>我们来看这样的处理顺序：</p>
<ul>
<li>判断待处理的数组中有多少元素，如果只有一个，返回</li>
</ul>
<ul>
<li>选取基准，利用基准将数组分成两部分，进行划分，小于等于基准的在左面，大于基准的在右面</li>
<li>将基准左面的数组重新执行第一步</li>
<li>将基准右面的数组重新执行第一步</li>
</ul>
<blockquote>
<p>待排序列：[6,5,4,3,2,1]</p>
<ul>
<li>==下标 5 基准 1==</li>
<li>[1, 5, 4, 3, 2, 6]</li>
<li>==下标 5 基准 6==</li>
<li>[1, 5, 4, 3, 2, 6]</li>
<li>==下标 4 基准 2==</li>
<li>[1, 2, 4, 3, 5, 6]</li>
<li>==下标 4 基准 5==</li>
<li>[1, 2, 4, 3, 5, 6]</li>
<li>==下标 3 基准 3==</li>
<li>[1, 2, 3, 4, 5, 6]</li>
</ul>
<p>如上所示，目前基准选择的是最右面的元素，第一次，选择1作为基准，第二次选择6作为基准，一次类推；</p>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">partation</span><span class="params">(l_A , left , right)</span>:</span></span><br><span class="line">    pivot = l_A[right]</span><br><span class="line">    pivot_index = left</span><br><span class="line">    <span class="comment"># print('下标',right,'基准',pivot)</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(left, right):</span><br><span class="line">        <span class="keyword">if</span> l_A[i] &lt;= pivot:</span><br><span class="line">            l_A[i] ,l_A[pivot_index] = l_A[pivot_index], l_A[i]</span><br><span class="line">            pivot_index += <span class="number">1</span></span><br><span class="line">    <span class="keyword">if</span> pivot_index != right:</span><br><span class="line">        l_A[pivot_index] , l_A[right] =  l_A[right] ,l_A[pivot_index]</span><br><span class="line">    <span class="comment"># print(l_A)</span></span><br><span class="line">    <span class="keyword">return</span> pivot_index</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">quick_sort</span><span class="params">(l_A, left , right)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> left &gt;= right:</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    pivot_index = partation(l_A ,left, right)</span><br><span class="line">    quick_sort(l_A,left,pivot_index <span class="number">-1</span>)</span><br><span class="line">    quick_sort(l_A,  pivot_index+<span class="number">1</span> , right)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    quick_sort(A,<span class="number">0</span>,len(A)<span class="number">-1</span>)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h4 id="2-2-2-随机快速排序"><a href="#2-2-2-随机快速排序" class="headerlink" title="2.2.2 随机快速排序"></a>2.2.2 随机快速排序</h4><p><img src="/blog/2018/08/07/algorithm/内部排序算法/random_quick.gif" alt="random_quick"></p>
<p>​    随机快速排序与快速排序的主要区别就在于基准的选择上，随机快排是随机的选择基准，然后</p>
<blockquote>
<p>待排序列：[6,5,4,3,2,1]</p>
<ul>
<li><p>==下标 4 基准 2==</p>
</li>
<li><p>[1, 2, 4, 3, 6, 5]</p>
</li>
<li><p>==下标 5 基准 5==</p>
</li>
<li><p>[1, 2, 4, 3, 5, 6]</p>
</li>
<li><p>==下标 2 基准 4==</p>
</li>
<li><p>[1, 2, 3, 4, 5, 6]</p>
<p>如上所示，</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> random</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">partation</span><span class="params">(l_A , left , right)</span>:</span></span><br><span class="line">    p = left + int((right - left + <span class="number">1</span>) * random.random())</span><br><span class="line">    l_A[p] ,l_A[right] = l_A[right], l_A[p]</span><br><span class="line">    pivot = l_A[right]</span><br><span class="line">    <span class="comment"># print('下标',p,'基准',pivot)</span></span><br><span class="line">    pivot_index = left</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(left, right):</span><br><span class="line">        <span class="keyword">if</span> l_A[i] &lt;= pivot:</span><br><span class="line">            l_A[i] ,l_A[pivot_index] = l_A[pivot_index], l_A[i]</span><br><span class="line">            pivot_index += <span class="number">1</span></span><br><span class="line">    <span class="keyword">if</span> pivot_index != right:</span><br><span class="line">        l_A[pivot_index] , l_A[right] =  l_A[right] ,l_A[pivot_index]</span><br><span class="line">    <span class="comment"># print(l_A)</span></span><br><span class="line">    <span class="keyword">return</span> pivot_index</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">quick_sort</span><span class="params">(l_A, left , right)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> left &gt;= right:</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    pivot_index = partation(l_A ,left, right)</span><br><span class="line">    quick_sort(l_A,left,pivot_index <span class="number">-1</span>)</span><br><span class="line">    quick_sort(l_A,  pivot_index+<span class="number">1</span> , right)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    quick_sort(A,<span class="number">0</span>,len(A)<span class="number">-1</span>)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h2 id="3、选择排序"><a href="#3、选择排序" class="headerlink" title="3、选择排序"></a>3、选择排序</h2><h3 id="3-1-选择排序"><a href="#3-1-选择排序" class="headerlink" title="3.1 选择排序"></a>3.1 选择排序</h3><p>​    <code>Selection Sort</code></p>
<p><img src="/blog/2018/08/07/algorithm/内部排序算法/chose.gif" alt="chose"></p>
<p>​    插入排序的基本思路就是从未排序的序列里面选出一个最小的，然后将至放到已排序列的尾部后面元素交换位置，一直到待排序列为0.</p>
<blockquote>
<p>待排序列：[5,4,3,2,1]</p>
<ul>
<li><p>[==1==,4,3,2,5]</p>
</li>
<li><p>[1,==2==,3,4,5]</p>
</li>
<li><p>[1,2,==3==,4,5]</p>
</li>
<li><p>[1,2,3,==4==,5]</p>
</li>
<li><p>[1,2,3,4,==5==]</p>
<p>如上所示，第一次，扫描全部序列，将最小的1选出来，然后将1与首位的数字5进行交换，然后第二次将最小数字2与数字4进行交换。</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">selection_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    n = len(l_A)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">0</span>,n):</span><br><span class="line">        swap_num = i</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(i + <span class="number">1</span>,n):</span><br><span class="line">            <span class="keyword">if</span> l_A[j] &lt; l_A[i]:</span><br><span class="line">                swap_num = j</span><br><span class="line">        <span class="keyword">if</span> swap_num != i:</span><br><span class="line">            l_A[i] , l_A[swap_num] = l_A[swap_num], l_A[i]</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = selection_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="3-2-堆排序"><a href="#3-2-堆排序" class="headerlink" title="3.2 堆排序"></a>3.2 堆排序</h3><p>​    <code>Heap Sort</code></p>
<p><img src="/blog/2018/08/07/algorithm/内部排序算法/heap.gif" alt="heap"></p>
<p>​    堆是完全二叉树，分为最大堆和最小堆，最大堆中，根节点都比其子节点要大，而最小堆中，根节点都比其子节点要小；</p>
<p>​    最大堆的应用场景，例如带有优先级的排队进程，当系统空闲，优先处理优先级高的；</p>
<p>​    最大堆主要有这样几个注意点：</p>
<ul>
<li><p>建堆</p>
</li>
<li><p>删除根节点</p>
</li>
<li><p>插入一个节点</p>
</li>
</ul>
<p>  使用堆排序，主要是利用根节点一直是最大的性质，将根节点与最后面的儿子节点位置对调，堆的大小减一， 然后进行堆调整，然后再将根节点与莫为节点对调，再调整成堆，然后循环递归；</p>
<p>所以，堆排序主要是下面几个步骤：</p>
<ul>
<li>将数组调整成堆</li>
<li>将根元素与堆的末尾元素对调，调整堆</li>
<li>重复第二步，直到堆的大小为1为止。</li>
</ul>
<blockquote>
<p>待排序列：[6,5,4,3,2,1]</p>
<ul>
<li><p>[5,4,3,2,1,==6==]</p>
</li>
<li><p>[4,3,2,1,==5,6==]</p>
</li>
<li><p>[3,2,1,==4,5,6==]</p>
</li>
<li><p>[2,1,==3,4,5,6==]</p>
</li>
<li><p>[==1,2,3,4,5,6==]</p>
<p>这一个较为特殊，默认就是堆的形式，第一步是调整成堆</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">heapify</span><span class="params">(l_A, node , size)</span>:</span></span><br><span class="line">    left_child = <span class="number">2</span> * node + <span class="number">1</span></span><br><span class="line">    right_child = <span class="number">2</span> * node + <span class="number">2</span></span><br><span class="line">    max = node</span><br><span class="line">    <span class="keyword">if</span> left_child &lt; size <span class="keyword">and</span> l_A[max] &lt; l_A[left_child] :</span><br><span class="line">        max = left_child</span><br><span class="line">    <span class="keyword">if</span> right_child &lt; size <span class="keyword">and</span> l_A[max] &lt; l_A[right_child] : </span><br><span class="line">        max = right_child</span><br><span class="line">    <span class="keyword">if</span> max != node:</span><br><span class="line">        l_A[max] , l_A[node] = l_A[node],l_A[max]</span><br><span class="line">        heapify(l_A, max , size)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">build_heap</span><span class="params">(l_A, size)</span>:</span></span><br><span class="line">    heap_size = (size - <span class="number">1</span>) // <span class="number">2</span></span><br><span class="line">    <span class="keyword">while</span> heap_size &gt;= <span class="number">0</span> :</span><br><span class="line">        heapify(l_A, heap_size , size)</span><br><span class="line">        heap_size -= <span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">heap_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    temp = build_heap(l_A, size)</span><br><span class="line">    <span class="keyword">while</span> size &gt; <span class="number">1</span>:</span><br><span class="line">        size -= <span class="number">1</span></span><br><span class="line">        l_A[<span class="number">0</span>],l_A[size] = l_A[size],l_A[<span class="number">0</span>] </span><br><span class="line">        heapify(l_A,<span class="number">0</span>, size)</span><br><span class="line">    <span class="keyword">return</span> temp</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = heap_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h2 id="4、插入排序"><a href="#4、插入排序" class="headerlink" title="4、插入排序"></a>4、插入排序</h2><h3 id="4-1-直接插入排序"><a href="#4-1-直接插入排序" class="headerlink" title="4.1 直接插入排序"></a>4.1 直接插入排序</h3><p><img src="/blog/2018/08/07/algorithm/内部排序算法/insert.gif" alt="insert"></p>
<p>​    直接插入排序也是将待排序列分成两部分，其一是左面排好序的，然后是右面待排序，首先将待排序的第一个元素取出来，与排好序的序列机芯从右向左的比对，如果小于，则将此元素向右移动，一直找到当前元素应该放在的位置。</p>
<blockquote>
<p>待排序列：[5,4,3,2,1]</p>
<ul>
<li><p>[==4,5==,3,2,1]</p>
</li>
<li><p>[==3,4,5==,2,1]</p>
</li>
<li><p>[==2,3,4,5==,1]</p>
</li>
<li><p>[==1,2,3,4,5==]</p>
<p>如上，以高亮表示排好序的元素，然后第一次从待排序中，取出4，然后与5比较，将5向后移位，然后将4放到首位，剩下元素依次进行。</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">insertion_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    n = len(l_A)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>,n):</span><br><span class="line">        get = l_A[i]</span><br><span class="line">        j = i - <span class="number">1</span></span><br><span class="line">        <span class="keyword">while</span> j &gt;= <span class="number">0</span> <span class="keyword">and</span> l_A[j] &gt; get:</span><br><span class="line">            l_A[j+<span class="number">1</span>] = l_A[j]</span><br><span class="line">            j = j - <span class="number">1</span></span><br><span class="line">        l_A[j+<span class="number">1</span>] = get</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = insertion_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="4-2-二分插入排序"><a href="#4-2-二分插入排序" class="headerlink" title="4.2 二分插入排序"></a>4.2 二分插入排序</h3><p>​    二分插入排序是直接插入排序的改进版，主要针对于需要比对次数多的场景，例如有一个较小的元素，需要比对多次才能确定要插入的位置，使用二分法，提高查找效率。</p>
<blockquote>
<p>待排序列：[6,5,4,3,2,1]</p>
<ul>
<li><p>[==5, 6==, 4, 3, 2, 1]</p>
</li>
<li><p>[==4, 5, 6==, 3, 2, 1]</p>
</li>
<li><p>[==3, 4, 5, 6==, 2, 1]</p>
</li>
<li><p>[==2, 3, 4, 5, 6==, 1]</p>
</li>
<li><p>[==1, 2, 3, 4, 5, 6==]</p>
<p>与前面基本相同，唯一不同的就是，在寻找要插入的位置的时候，使用了二分查找法。</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">binary_insertion_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    n = len(l_A)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>, n):</span><br><span class="line">        get = l_A[i]</span><br><span class="line">        left = <span class="number">0</span></span><br><span class="line">        right = i <span class="number">-1</span></span><br><span class="line">        <span class="keyword">while</span> left &lt;= right:</span><br><span class="line">            mid = (left+right)//<span class="number">2</span></span><br><span class="line">            <span class="keyword">if</span> l_A[i] &lt; l_A[mid]:</span><br><span class="line">                right = mid - <span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                left = mid + <span class="number">1</span></span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(i,left,<span class="number">-1</span>):</span><br><span class="line">            l_A[j] = l_A[j<span class="number">-1</span>]</span><br><span class="line">        l_A[left] = get</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = binary_insertion_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="4-3-希尔排序"><a href="#4-3-希尔排序" class="headerlink" title="4.3 希尔排序"></a>4.3 希尔排序</h3><p>​    前面两种插入排序需要移动元素的次数还是太多，是否能够一次将元素移动多个位置，尽可能接近他本来的位置，希尔排序的基本思路就是使用一个递减增量，将待排序列分成多个子序列，进行插入排序，然后最后使用一次增量为1的直接插入排序。</p>
<blockquote>
<p>希尔排序是基于插入排序的以下两点性质而提出改进方法的：</p>
<ul>
<li>插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。</li>
<li>但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。</li>
</ul>
</blockquote>
<blockquote>
<p>待排序列：[6,5,4,3,2,1]</p>
<p>增量序列：[4,1]</p>
<ol>
<li><p>首先，取出增量4，将待排序列分成几个子序列：</p>
<ul>
<li>[6,2]</li>
<li>[5,1]</li>
<li>[4]</li>
<li>[3]</li>
</ul>
<p>分成了4个子序列，然后分别使用插入排序，对这4个子序列进行排序<br>得到下面的结果：<br>[2,1,4,3,6,5]</p>
<p>可以看到，6,5直接被移动到靠近他们办类的位置上了；</p>
</li>
<li><p>然后，使用增量1，再来使用插入排序</p>
</li>
</ol>
<ul>
<li>[==1, 2==, 4, 3, 6, 5]</li>
<li>[==1, 2, 4==, 3, 6, 5]</li>
<li>[==1, 2, 3, 4==, 6, 5]</li>
<li>[==1, 2, 3, 4, 6==, 5]</li>
<li>[==1, 2, 3, 4, 5, 6==]</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">shell_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    n = len(l_A)</span><br><span class="line">    h = n // <span class="number">2</span> </span><br><span class="line">    <span class="keyword">while</span> h &gt;= <span class="number">1</span>:</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(h,n):</span><br><span class="line">            get = l_A[i]</span><br><span class="line">            j = i - h</span><br><span class="line">            <span class="keyword">while</span> j &gt;= <span class="number">0</span> <span class="keyword">and</span> l_A[j] &gt; get:</span><br><span class="line">                l_A[j + h] = l_A[j]</span><br><span class="line">                j -= h</span><br><span class="line">            l_A[j+h] = get</span><br><span class="line">        h = h // <span class="number">2</span></span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = shell_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<p>​    上面采用的增量序列为[3,1]，是利用<code>h = n // 2</code>获得，我们可以使用增量函数，或者直接使用增量序列。</p>
<h2 id="5、归并排序"><a href="#5、归并排序" class="headerlink" title="5、归并排序"></a>5、归并排序</h2><p><img src="/blog/2018/08/07/algorithm/内部排序算法/merge.gif" alt="merge"></p>
<p>​    归并排序是建立在分治法上的典型应用，分为递归实现和非递归实现</p>
<blockquote>
<p>基本步骤：</p>
<ul>
<li>创建一个数组，能够存放两个已经有序的数组</li>
<li>两个分别指向两个有序数组起始位置的指针</li>
<li>比较指针指向的两个元素，将其中较小的放入和数组，指针加一</li>
<li>重复上面步骤，直到指针指向有序数组的末尾</li>
<li>将另一个未指向末尾的数组放入到和数组中</li>
</ul>
</blockquote>
<blockquote>
<p>递归实现：[6,5,4,3,2,1]</p>
<ul>
<li><p>[5, 6]</p>
</li>
<li><p>[4, 5, 6]</p>
</li>
<li><p>[2, 3]</p>
</li>
<li><p>[1, 2, 3]</p>
</li>
<li><p>[1, 2, 3, 4, 5, 6]</p>
<p>上面为归并函数一次处理的有序数组，第一个表示将[6],[5]进行归并，以此类推；</p>
</li>
<li><p>[5, 6, 4, 3, 2, 1]</p>
</li>
<li><p>[4, 5, 6, 3, 2, 1]</p>
</li>
<li><p>[4, 5, 6, 2, 3, 1]</p>
</li>
<li><p>[4, 5, 6, 1, 2, 3]</p>
</li>
<li><p>[1, 2, 3, 4, 5, 6]</p>
<p>上面表示待排数字的依次变化</p>
</li>
</ul>
</blockquote>
<blockquote>
<p>非递归实现：[6,5,4,3,2,1]</p>
<ul>
<li><p>[5, 6]</p>
</li>
<li><p>[3, 4]</p>
</li>
<li><p>[1, 2]</p>
</li>
<li><p>[3, 4, 5, 6]</p>
</li>
<li><p>[1, 2, 3, 4, 5, 6]</p>
<p>上面表示非递归模式下，依次进行处理的有序数列；</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">merge</span><span class="params">(l_A, left, mid, right)</span>:</span></span><br><span class="line">    temp = []</span><br><span class="line">    i = left</span><br><span class="line">    j = mid + <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> i &lt;= mid <span class="keyword">and</span> j &lt;= right:</span><br><span class="line">        <span class="keyword">if</span> l_A[i] &lt;= l_A[j]:</span><br><span class="line">            temp.append(l_A[i])</span><br><span class="line">            i += <span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            temp.append(l_A[j])</span><br><span class="line">            j += <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> i &lt;= mid:</span><br><span class="line">        temp.append(l_A[i])</span><br><span class="line">        i += <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> j &lt;= right:</span><br><span class="line">        temp.append(j)</span><br><span class="line">        j += <span class="number">1</span></span><br><span class="line">    l_A[left:right+<span class="number">1</span>] = temp</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">merge_recursion</span><span class="params">(l_A, left , right)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> left == right:</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    mid = (left + right) // <span class="number">2</span></span><br><span class="line">    merge_recursion(l_A,left,mid)</span><br><span class="line">    merge_recursion(l_A,mid+<span class="number">1</span>,right)</span><br><span class="line">    merge(l_A,left,mid,right)</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">merge_iteration</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    length = len(l_A)</span><br><span class="line">    i = <span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span> i &lt; length :</span><br><span class="line">        left = <span class="number">0</span></span><br><span class="line">        <span class="keyword">while</span> left + i &lt; length:</span><br><span class="line">            mid = left + i <span class="number">-1</span></span><br><span class="line">            <span class="keyword">if</span> mid + i &lt; length:</span><br><span class="line">                right = mid + i</span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                right = length - <span class="number">1</span></span><br><span class="line">            merge(l_A,left,mid,right)</span><br><span class="line">            left = right + <span class="number">1</span></span><br><span class="line">        i *= <span class="number">2</span></span><br><span class="line">        <span class="comment"># print(l_A)</span></span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    <span class="comment"># merge_recursion(A,0,len(A)-1)</span></span><br><span class="line">    merge_iteration(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h2 id="6、分布排序"><a href="#6、分布排序" class="headerlink" title="6、分布排序"></a>6、分布排序</h2><h3 id="6-1-计数排序"><a href="#6-1-计数排序" class="headerlink" title="6.1 计数排序"></a>6.1 计数排序</h3><p>​    <code>Counting Sort</code></p>
<p><img src="/blog/2018/08/07/algorithm/内部排序算法/counting.gif" alt="counting"></p>
<p>​    计数排序的思想：假如现在有10个数，[2,3,4,5,1,2,3,4,2,5]，如何能直接确定数字2在排好序的数组里面的位置呢？假如现在已经将数组中所有小于2的数的总数量统计了，如上面的数组，小于2的数一共有1个，那么在排好序的数组里面，2是从下标为1的数组中开始存储，占有的存储单元就是2个个数。</p>
<p>计数排序的步骤：</p>
<ul>
<li>待排数组为A</li>
</ul>
<ul>
<li>初始化数组B，数据全部为0，数组大小为待排数组中最大的元素+1</li>
<li>扫描待排数组，统计元素个数，存放在数组B对应的下标中，例如3的个数，存放在B[3]中</li>
<li>然后，数组B中的每一个元素都是&lt;=当前下标数据之和<ul>
<li>举个例子，如果B=[1,0,2,3,4,5]</li>
<li>B[0] = B[0]</li>
<li>B[1] = B[1]+B[0]</li>
<li>B[2] = B[2]+B[1]+B[0]</li>
<li>使用循环控制的话，就能够使用如下表示：</li>
<li>B[0] = B[0]</li>
<li>B[1] = B[1]+B[0]</li>
<li>B[2] = B[2]+B[1]</li>
<li>然后，我们就得到了每一个元素在排好序的数组中的最后一个位置</li>
</ul>
</li>
<li>然后，创建数组C，与待排数组大小相同</li>
<li>从后向前扫描A，将出现的数放到C，存放位置为B[i],然后将i减一，表示下一个数字i的位置</li>
</ul>
<blockquote>
<p>待排数组：[6,5,4,3,2,1]</p>
<ul>
<li><p>数组B：[0,1,1,1,1,1,1]</p>
</li>
<li><p>累加B：[0,1,2,3,4,5,6]</p>
</li>
<li><p>数组C：[1,0,0,0,0,0]</p>
</li>
<li><p>数组C：[1,2,0,0,0,0]</p>
</li>
<li><p>数组C：[1,2,3,0,0,0]</p>
</li>
<li><p>数组C：[1,2,3,4,0,0]</p>
</li>
<li><p>数组C：[1,2,3,4,5,0]</p>
</li>
<li><p>数组C：[1,2,3,4,5,6]</p>
<p>需要注意的是，我们计数是从1开始，二存储的时候，下标从0开始，所以需要将数组B中的数字减一，作为存储在C中的下标。</p>
</li>
</ul>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">counting_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    <span class="string">'''</span></span><br><span class="line"><span class="string">        l_A：待排数组</span></span><br><span class="line"><span class="string">    '''</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    nums = max(l_A) + <span class="number">1</span></span><br><span class="line">    temp_position_len = nums + <span class="number">1</span></span><br><span class="line">    temp_position = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(temp_position_len)]</span><br><span class="line">    temp_position_right = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(size)]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size):</span><br><span class="line">        temp_position[l_A[i]] += <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>, len(temp_position)):</span><br><span class="line">        temp_position[i] += temp_position[i<span class="number">-1</span>]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>):</span><br><span class="line">        temp_position_right[temp_position[l_A[i]] <span class="number">-1</span>] = l_A[i]</span><br><span class="line">        temp_position[l_A[i]] -= <span class="number">1</span></span><br><span class="line">    l_A = temp_position_right</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = counting_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="6-2-基数排序"><a href="#6-2-基数排序" class="headerlink" title="6.2 基数排序"></a>6.2 基数排序</h3><p>​    <code>Radix Sort</code><img src="/blog/2018/08/07/algorithm/内部排序算法/radix.gif" alt="radix"></p>
<p>​    基数排序，其原理为利用数字不同位置的数码，进行排序；假如有这样的数组，[12,45,6,77,88]，我们发现数字最多两位，数码有10个，也就是<code>0~9</code>，我们创建10个数组，分别代表<code>0~9</code>, 第一次，将最低位相同的数字放到同样的数组里面，也就是最低位为1的数字放到表示1的数组中，将待排数组从前往后扫描，然后从第0个数组开始，将数据取出来，为了保障是稳定性，取出数据的时候，从后往前取出来，然后在扫描第二次，判断第二个数码；</p>
<blockquote>
<p>待排数组: [89,88,77,6,5,4,3,2,1]</p>
<p>第一次扫描：</p>
<p>0数组：[]</p>
<p>1数组：[1]</p>
<p>2数组：[2]</p>
<p>3数组：[3]</p>
<p>4数组：[4]</p>
<p>5数组：[5]</p>
<p>6数组：[6]</p>
<p>7数组：[77]</p>
<p>8数组：[88]</p>
<p>9数组：[89]</p>
<p>放回待排数组：[1,2,3,4,5,6,77,88,89]</p>
<p>第2次扫描：</p>
<p>0数组：[1,2,3,4,5,6]</p>
<p>1数组：[]</p>
<p>2数组：[]</p>
<p>3数组：[]</p>
<p>4数组：[]</p>
<p>5数组：[]</p>
<p>6数组：[]</p>
<p>7数组：[]</p>
<p>8数组：[88,89]</p>
<p>9数组：[]</p>
<p>放回待排数组：[1,2,3,4,5,6,77,88,89]</p>
</blockquote>
<p>​    根据上面的思路，有两种实现思路：</p>
<blockquote>
<p>第一种：</p>
<p>​    创建多个数组，每个数组都代表一个数码，按照最大的数的位数进行循环操作</p>
<p>第二种：</p>
<p>​    我们发现，在按照数码放到不同的素组里的思路，与前面的计数有些相似，如果按照不同的位数，进行计数排序，并且同时保证稳定性，也可以实现我们想要的操作。</p>
</blockquote>
<p><strong>第一种</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">get_digit</span><span class="params">(digit,position)</span>:</span></span><br><span class="line">    num = digit // <span class="number">10</span> ** position % <span class="number">10</span></span><br><span class="line">    <span class="keyword">return</span> num     </span><br><span class="line">    </span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">radix_sort</span><span class="params">(l_A, digits, nums)</span>:</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    temp_nums = [[] <span class="keyword">for</span> i <span class="keyword">in</span> range(digits)]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(nums):</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(size):</span><br><span class="line">            temp_nums[get_digit(l_A[j],i)].append(l_A[j])</span><br><span class="line">        l_A = []</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(digits):</span><br><span class="line">            <span class="keyword">for</span> temp_item <span class="keyword">in</span> range(len(temp_nums[j])):</span><br><span class="line">                l_A.append(temp_nums[j].pop(<span class="number">0</span>))</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    <span class="comment"># A = [6,5,4,3,2,1]</span></span><br><span class="line">    A = [<span class="number">33</span>,<span class="number">44</span>,<span class="number">13</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">33</span>,<span class="number">45</span>,<span class="number">90</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = radix_sort(A,<span class="number">10</span>,<span class="number">2</span> )</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<p><strong>第二种</strong></p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">get_digit</span><span class="params">(digit,position)</span>:</span></span><br><span class="line">    num = digit // <span class="number">10</span> ** position % <span class="number">10</span></span><br><span class="line">    <span class="keyword">return</span> num     </span><br><span class="line">    </span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">counting_sort</span><span class="params">(l_A ,nums,position,size)</span>:</span></span><br><span class="line">    temp_position_len = nums</span><br><span class="line">    temp_position = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(temp_position_len)]</span><br><span class="line">    temp_position_right = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(size)]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size):</span><br><span class="line">        temp_position[get_digit(l_A[i],position)] += <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>, len(temp_position)):</span><br><span class="line">        temp_position[i] += temp_position[i<span class="number">-1</span>]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>):</span><br><span class="line">        temp_position_right[temp_position[get_digit(l_A[i],position)] <span class="number">-1</span>] = l_A[i]</span><br><span class="line">        temp_position[get_digit(l_A[i],position)] -= <span class="number">1</span></span><br><span class="line">    l_A = temp_position_right</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">radix_sort</span><span class="params">(l_A,digits, nums)</span>:</span></span><br><span class="line">    <span class="string">'''</span></span><br><span class="line"><span class="string">        l_A：待排数组</span></span><br><span class="line"><span class="string">        digits：数码个数</span></span><br><span class="line"><span class="string">        nums：最大数的位数</span></span><br><span class="line"><span class="string">    '''</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(nums):</span><br><span class="line">        l_A = counting_sort(l_A, digits,i, size)</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">33</span>,<span class="number">44</span>,<span class="number">1000</span>,<span class="number">13</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">33</span>,<span class="number">45</span>,<span class="number">990</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = radix_sort(A,<span class="number">10</span>,<span class="number">4</span> )</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="6-3-鸽巢排序"><a href="#6-3-鸽巢排序" class="headerlink" title="6.3 鸽巢排序"></a>6.3 鸽巢排序</h3><p>​    <code>Pigeonhole Sort</code></p>
<p>​    鸽巢排序是一中种高速排序，但是需要很大的辅助空间；</p>
<p>​    例如待排数组：[5,3,2,6,33,77]，就需要77-2+1=76个辅助空间</p>
<p>​    排序思路：</p>
<ul>
<li>申请辅助空间</li>
<li>得到数组中的最大、最小值</li>
<li>扫描数组，将每个数减去最小值的数作为下标，将此下标中的数增加1</li>
<li>扫描辅助数组，将对应下标加上最小值，得到原来的数，放入待排数组</li>
</ul>
<blockquote>
<p>待排数组：[5,3,2,5,7]</p>
<p>辅助空间：[0,0,0,0,0,0]</p>
<p>最大值：7</p>
<p>最小值：2</p>
<p>扫描数组，处理辅助数组：[1,1,0,2,0,1]</p>
<p>扫描辅助数组，得到排序数组：[2,3,5,5,7]</p>
</blockquote>
<p>​    由上面可得，如果数据范围太大，或者说重复的数据很少，使用鸽巢排序不划算，只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">pigeonhole_sort</span><span class="params">(l_A)</span>:</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    <span class="keyword">if</span> size &gt; <span class="number">1</span>:</span><br><span class="line">        max_value = max(l_A)</span><br><span class="line">        min_value = min(l_A)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line">    assistant = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(max_value - min_value + <span class="number">1</span>)]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size):</span><br><span class="line">        assistant[l_A[i]-min_value] += <span class="number">1</span></span><br><span class="line">    l_A = []</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len(assistant)):</span><br><span class="line">        <span class="keyword">while</span> assistant[i] &gt;= <span class="number">1</span>:</span><br><span class="line">            l_A.append(min_value+i)</span><br><span class="line">            assistant[i] -= <span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = pigeonhole_sort(A)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h3 id="6-4-桶排序"><a href="#6-4-桶排序" class="headerlink" title="6.4 桶排序"></a>6.4 桶排序</h3><p>​    <code>Bucket Sort</code></p>
<p>​    桶排序是将待排序列放到有限数量的桶里，然后在每个桶里，使用其他的排序算法，进行排序；桶由计数所决定；</p>
<p>​    基本思路：</p>
<ul>
<li>确定桶的数量<ul>
<li>例如，我们输入的数据都在0到50之间，那么我们确定5个桶，<code>0~10</code>,<code>11~20</code>等</li>
</ul>
</li>
<li>根据桶的数量，确定映射函数，也就是将能够确定相同的桶的依据<ul>
<li>例如，根据上面说的，我们设置数据的十位数作为分桶依据，映射函数就是<code>in/10</code></li>
</ul>
</li>
<li>将数据分开，放在不同的桶中，也就是记住不同的桶之间的边界数据<ul>
<li>比如说，使用计数算法，将不同的边界分开</li>
</ul>
</li>
<li>在桶内使用排序算法进行排序</li>
</ul>
<blockquote>
<p>待排序列：[33,9,11,4,22,44,5,6]</p>
<p>桶的数量：5</p>
<p>映射函数：x//10   ==python中，<code>//</code>表示整除==</p>
<p>分桶：[9,4,5,6,11,22,33,44]</p>
<p>边界数据：[4,1,1,1,1]</p>
<p>桶内排序：[4,5,6,9,11,22,33,44]</p>
</blockquote>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">map2bucket</span><span class="params">(number)</span>:</span></span><br><span class="line">    <span class="keyword">return</span> number // <span class="number">10</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">insert_sort</span><span class="params">(l_A,left,right)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> left == right:</span><br><span class="line">        <span class="keyword">return</span> l_A</span><br><span class="line">    length = right - left + <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>,length):</span><br><span class="line">        get = l_A[i]</span><br><span class="line">        j = i<span class="number">-1</span></span><br><span class="line">        <span class="keyword">while</span> j &gt;=<span class="number">0</span> <span class="keyword">and</span> l_A[j] &gt; get:</span><br><span class="line">            l_A[j+<span class="number">1</span>] = l_A[j]</span><br><span class="line">            j -= <span class="number">1</span></span><br><span class="line">        l_A[j+<span class="number">1</span>] = get</span><br><span class="line">    <span class="keyword">return</span> l_A</span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">counting_sort</span><span class="params">(l_A, nums)</span>:</span></span><br><span class="line">    <span class="string">'''</span></span><br><span class="line"><span class="string">        l_A：待排数组</span></span><br><span class="line"><span class="string">        nums：桶的数量</span></span><br><span class="line"><span class="string">    '''</span></span><br><span class="line">    size = len(l_A)</span><br><span class="line">    temp_position_len = nums</span><br><span class="line">    temp_position = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(temp_position_len)]</span><br><span class="line">    temp_position_right = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(size)]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size):</span><br><span class="line">        temp_position[map2bucket(l_A[i])] += <span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>, len(temp_position)):</span><br><span class="line">        temp_position[i] += temp_position[i<span class="number">-1</span>]</span><br><span class="line">    boundary = temp_position.copy()</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(size<span class="number">-1</span>,<span class="number">-1</span>,<span class="number">-1</span>):</span><br><span class="line">        temp_position_right[temp_position[map2bucket(l_A[i])] <span class="number">-1</span>] = l_A[i]</span><br><span class="line">        temp_position[map2bucket(l_A[i])] -= <span class="number">1</span></span><br><span class="line">    l_A = temp_position_right</span><br><span class="line">    <span class="keyword">return</span> l_A, boundary</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bucket_sort</span><span class="params">(l_A, bucket_nums)</span>:</span></span><br><span class="line">    temp_l_A, boundary = counting_sort(l_A, bucket_nums)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(bucket_nums):</span><br><span class="line">        left = boundary[i]</span><br><span class="line">        <span class="keyword">if</span> left &gt;= len(l_A):</span><br><span class="line">            left = <span class="number">0</span></span><br><span class="line">        <span class="keyword">if</span> i &gt;= bucket_nums - <span class="number">1</span> :</span><br><span class="line">            right = boundary[<span class="number">0</span>] - <span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            right = boundary[i+<span class="number">1</span>] <span class="number">-1</span></span><br><span class="line">        temp_l_A = insert_sort(temp_l_A, left,right)</span><br><span class="line">    <span class="keyword">return</span> temp_l_A</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line">    A = [<span class="number">6</span>,<span class="number">5</span>,<span class="number">4</span>,<span class="number">3</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">11</span>,<span class="number">33</span>,<span class="number">22</span>,<span class="number">44</span>]</span><br><span class="line">    A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> A])</span><br><span class="line">    sorted_A = bucket_sort(A, <span class="number">5</span>)</span><br><span class="line">    sorted_A_str = <span class="string">","</span>.join([str(i) <span class="keyword">for</span> i <span class="keyword">in</span> sorted_A])</span><br><span class="line">    print(<span class="string">"待排序列："</span>,A_str)</span><br><span class="line">    print(<span class="string">"已排序列："</span>,sorted_A_str)</span><br></pre></td></tr></table></figure>
<h2 id="7、参考资料"><a href="#7、参考资料" class="headerlink" title="7、参考资料"></a>7、参考资料</h2><p>数据结构与算法动态可视化： <a href="https://visualgo.net/zh" target="_blank" rel="noopener">https://visualgo.net/zh</a></p>
<p>可视化排序：<a href="http://panthema.net/2013/sound-of-sorting/#" target="_blank" rel="noopener">http://panthema.net/2013/sound-of-sorting/#</a></p>
<p>wiki排序算法：<a href="https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95" target="_blank" rel="noopener">排序算法</a></p>

      
    </div>

    

    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/sorting/" rel="tag"># sorting</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/2018/08/07/leetcode/LeetCode: 1. 两数之和/" rel="next" title="LeetCode 1. 两数之和">
                <i class="fa fa-chevron-left"></i> LeetCode 1. 两数之和
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>


  </div>


          </div>
          

  
    <div class="comments" id="comments">
    </div>
  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/blog/images/avatar.jpg"
                alt="夜行" />
            
              <p class="site-author-name" itemprop="name">夜行</p>
              <p class="site-description motion-element" itemprop="description">天行健，君子以自强不息！</p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/blog/archives/">
                
                    <span class="site-state-item-count">386</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  <a href="/blog/categories/index.html">
                    
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">2</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/blog/tags/index.html">
                    
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">2</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  <a href="https://github.com/zhishengqianjun123" target="_blank" title="GitHub"><i class="fa fa-fw fa-github"></i>GitHub</a>
                  
                </span>
              
                <span class="links-of-author-item">
                  <a href="mailto:zhishengqianjun@gmail.com" target="_blank" title="E-Mail"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  
                </span>
              
            </div>
          

          
          

          
          

          
            
          
          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#前言"><span class="nav-text">前言</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#1、排序算法的分类"><span class="nav-text">1、排序算法的分类</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2、交换排序"><span class="nav-text">2、交换排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#2-1-冒泡排序"><span class="nav-text">2.1 冒泡排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#2-1-1-直接冒泡排序"><span class="nav-text">2.1.1 直接冒泡排序</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-1-2-鸡尾酒排序"><span class="nav-text">2.1.2 鸡尾酒排序</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-1-3-梳排序"><span class="nav-text">2.1.3 梳排序</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-2-快速排序"><span class="nav-text">2.2 快速排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#2-2-1-快速排序"><span class="nav-text">2.2.1 快速排序</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-2-2-随机快速排序"><span class="nav-text">2.2.2 随机快速排序</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3、选择排序"><span class="nav-text">3、选择排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#3-1-选择排序"><span class="nav-text">3.1 选择排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-2-堆排序"><span class="nav-text">3.2 堆排序</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#4、插入排序"><span class="nav-text">4、插入排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#4-1-直接插入排序"><span class="nav-text">4.1 直接插入排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-2-二分插入排序"><span class="nav-text">4.2 二分插入排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-3-希尔排序"><span class="nav-text">4.3 希尔排序</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5、归并排序"><span class="nav-text">5、归并排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#6、分布排序"><span class="nav-text">6、分布排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#6-1-计数排序"><span class="nav-text">6.1 计数排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-2-基数排序"><span class="nav-text">6.2 基数排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-3-鸽巢排序"><span class="nav-text">6.3 鸽巢排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#6-4-桶排序"><span class="nav-text">6.4 桶排序</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#7、参考资料"><span class="nav-text">7、参考资料</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2018</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">夜行</span>

  

  
</div>











        
<div class="busuanzi-count">
  <script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv" title="总访客量">
      <i class="fa fa-user"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
    </span>
  

  
    <span class="site-pv" title="总访问量">
      <i class="fa fa-eye"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
    </span>
  
</div>









        
      </div>
    </footer>

    

    
	
    

    
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  
    <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=6.3.0"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=6.3.0"></script>



  
  


  <script type="text/javascript" src="/blog/js/src/affix.js?v=6.3.0"></script>

  <script type="text/javascript" src="/blog/js/src/schemes/pisces.js?v=6.3.0"></script>



  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=6.3.0"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=6.3.0"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=6.3.0"></script>



  



  








  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  
  
  <script src="//unpkg.com/valine/dist/Valine.min.js"></script>
  
  <script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(function (item) {
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: false,
        appId: 'qluXerUVutA7CjS8IgGYE7wg-gzGzoHsz',
        appKey: 'kkrJimHdrtGVpP0goHXGtGDW',
        placeholder: 'Just go go',
        avatar:'mm',
        meta:guest,
        pageSize:'10' || 10,
        visitor: false
    });
  </script>



  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/blog/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  
  

  
    
      <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      },
      TeX: {equationNumbers: { autoNumber: "AMS" }}
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<script type="text/javascript" src="//cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

    
  


  
  

  

  

  

  

  

</body>
</html>
